package com.moyoutian.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 229. 求众数 II
 * <p>
 * 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：[3,2,3]
 * <p>
 * 输出：[3]
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [1]
 * <p>
 * 输出：[1]
 * <p>
 * 示例 3：
 * <p>
 * 输入：[1,1,1,3,3,2,2,2]
 * <p>
 * 输出：[1,2]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 5 * 104
 * -109 <= nums[i] <= 109
 */
public class Demo229 {
    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 3};
        System.out.println(majorityElement(nums));
    }

    public static List<Integer> majorityElement(int[] nums) {
        if (nums == null) {
            return new ArrayList<>(0);
        }
        int compare = nums.length / 3;
        int one = nums[0], tow = nums[0];
        int one_count = 0, tow_count = 0;
        for (int num : nums) {
            if (one == num) {
                one_count++;
            } else if (tow == num) {
                tow_count++;
            } else {
                if (one_count <= 0) {
                    one = num;
                    one_count = 1;
                } else if (tow_count <= 0) {
                    tow = num;
                    tow_count = 1;
                } else {
                    one_count--;
                    tow_count--;
                }
            }
        }

        List<Integer> re = null;
        if (one_count > 0 || tow_count > 0) {
            re = new ArrayList<>(2);
            //重新初始化
            one_count = 0;
            //重新初始化
            tow_count = 0;
            for (int num : nums) {
                if (one == num) {
                    one_count++;
                } else if (tow == num) {
                    tow_count++;
                }
            }
            if (tow_count > compare) {
                re.add(tow);
            }
            if (one_count > compare) {
                re.add(one);
            }
        }
        return re;
    }


    /**
     * 无脑
     */
    public static List<Integer> majorityElementBrainless(int[] nums) {
        if (nums == null) {
            return new ArrayList<>(0);
        }
        List<Integer> re = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        map.forEach((k, v) -> {
            if (v > nums.length / 3) {
                re.add(k);
            }
        });
        return re;
    }
}
